A conventional paper road map can be helpful when planning a route for a trip. However, a paper road map is limited in how much detail and information is available to the user. A computerized road-mapping program overcomes this problem with its ability to store large amounts of map information in memory. In this manner, a user is able to interact with the computerized road-mapping program to see a richly detailed map.
With the advent of large capacity memory storage devices, such as CD-ROMs, some computerized road-mapping programs are capable of representing very large and extremely detailed road maps. For example, a map of the entire United States having street-level information typically requires millions of map elements. These map elements represent transportation thoroughfares or roads and the end points of such thoroughfares. In some computerized road-mapping programs, a link is a type of map element representing a thoroughfare on the map. A node is a type of map element representing one of the end points of a link. The map elements may also contain other related information or attributes, such as whether a thoroughfare is a toll road or is characterized as a scenic thoroughfare. This additional information is helpful when attempting to plan a trip using a computerized road-mapping program. For example, the computerized road-mapping program can determine a particular route for a user based on the user's preferences for scenic thoroughfares instead of interstate highways.
As an increasing quantity (amount) of map information is stored, most computerized road-mapping programs begin to take longer to access the map information describing each map element. It is simply an issue of looking for a needle in a larger haystack. In other words, feature rich and large maps can become painfully slow to use. This is undesirable because the user may quickly become frustrated and dissatisfied when using such a slow computerized road-mapping program. Thus, there is a need to compactly store map elements to allow a large amount of information to be stored while still maintaining the ability to quickly access a map element when calculating a route across the map.
One possible solution is merely to increase the amount of storage space on the memory storage device. This possible approach may alleviate the need to compactly store the map elements. However, this approach does not address the increased access time typically experienced when storing data on larger memory storage devices. Finding the data takes longer because there is more memory to search when seeking to access a specific map element in the stored data. Furthermore, computer resources, such as memory space, can be limited. CD-ROMs are large, but they are still finite in memory storage capacity. Therefore, merely increasing the amount of memory used when storing the map elements representing the map does not solve the problem.
A solution for quickly accessing map elements is used in previous versions of a computerized road-mapping program called "AUTOMAP TRIP PLANNER", developed and distributed by Microsoft Corporation of Redmond, Wash. This program divides up the map into geographic regions. A given region's map information is stored within a predetermined block of memory. The map information includes information describing different kinds of map elements, such as link elements and node elements.
The information describing these map elements (nodes & links) is usually sequentially stored in a memory block. An index describes which memory block contains which map element. Accessing a particular map element usually involves a binary search of the index to determine which block contains the map element and then a binary search of the determined block for the map element. This solution used in previous versions of the "AUTOMAP TRIP PLANNER" program is adequate when a map has a relatively small number of map elements, such as 40,000. However, as the number of map elements grows larger in terms of orders of magnitude, this type of index/searching-based solution for accessing a map element can become undesirably time consuming. Furthermore, this type of index/searching-based solution does not attempt to address the problem of maintaining a relatively small memory storage footprint when representing a large amount of information (e.g., a large number of map elements representing a very large and detailed map).
Thus, there is a need for a system for storing, referencing, and accessing information about a map, which (1) reduces the amount of memory storage space required to represent the map, (2) maintains the ability to quickly access a map element, (3) does not require binary searching to find a map element in memory, and (4) does not require the map elements to be sequentially stored and referenced. In summary, such a system allows very rapid, non-sequential access to the map elements when a computerized road-mapping program is calculating a route across the map.